"""
三壶谜题：
有一个充满水的8品脱的水壶和两个空水壶（容积分别是5品脱和3品脱）。
通过将水壶完全倒满水和将水壶的水完全倒空这两种方式，在其中的一个水壶中得到4品脱的水。
"""


class node:  # 创建树节点
    def __init__(self, data):
        self.data = data  # 存储三个壶的容量状态
        self.per = None  # 存储上一时刻三个壶的容量状态


def pour(n):  # 扩展子节点
    r_list = n.data  # 记录当前三个水壶的容量状态
    max_list = [8, 5, 3]  # 水壶的最大容量
    # 每次就是操作两个水壶，进行倾倒动作
    for i, j in ((0, 1), (0, 2), (1, 2), (1, 0), (2, 0), (2, 1)):
        if r_list[i] != 0:
            n_list = r_list.copy()  # 初始化下一结点的水壶状态
            if r_list[i] + r_list[j] > max_list[j]:  # i加j的容量大于j的最大容量
                n_list[i] = r_list[i] - (max_list[j] - r_list[j])  # 把j倒满后,记录n_list[i]
                n_list[j] = max_list[j]  # 记录n_list[j]
            else:
                # 否则就可以全到给j
                n_list[j] = r_list[i] + r_list[j]  # n_list[j]就等于i，j 容量相加
                n_list[i] = 0  # r_list[i]全倒出了
            flag = True  # 记录水壶的状态是否已经发生过（扩展过）
            for one in closed_list:  # 遍历被扩展过的这些节点
                if one.data == n_list:  # 比较当前水壶状态和以往记录过得水壶状态，如果是已经产生过的就不再继续扩展
                    flag = False
            if flag:
                print("扩展的新节点是：", n_list)
                new_node = node(n_list)  # 创建新节点存储水壶的新状态
                new_node.per = n  # 将前驱保存，后面好打印出这条路径所有的节点
                open_list.append(new_node)  # 已找到却未被扩展的子节点n_list


def BFS_node(root_1):  # 递归查找子节点的扩展状态以及查验是否找到4品脱的水壶
    n = root_1
    print("当前节点：", n.data)
    if open_list is None:
        return "没有找到4品脱的水"
    nodelist = n.data
    if 4 in nodelist:
        print("找到了4品脱的水")
        print_node(n)
        return "找到了4品脱的水"
    closed_list.append(open_list.pop(0))  # open_list中的那个被扩展节点被推出，添加到closed_list中
    pour(n)  # 扩展子节点
    print("*******")
    BFS_node(open_list[0])  # 继续扩展在pour()中被添加入open_list表的节点


def print_node(n):  # 打印正确的水壶操作路径
    if n.per is None:  # 前面没有了就停止
        return ""
    print(n.data)
    print_node(n.per)  # 继续打印前一个时间水壶状态


# 初始化数据
root = node([8, 0, 0])  # root是node类的一个对象
open_list = [root]  # 存储已找到却未被扩展的子节点
closed_list = []  # 存储已找到且被扩展的子节点
BFS_node(open_list[0])
